/*************************************************************************
 * File Name:    Interleaving_String.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 02 Nov 2013 08:27:43 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Interleaving String
 | Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
 |
 | For example,
 | Given:
 | s1 = "aabcc",
 | s2 = "dbbca",
 |
 | When s3 = "aadbbcbcac", return true.
 | When s3 = "aadbbbaccc", return false.
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size();
        int n = s2.size();
        
        if (m + n != s3.size()) return false;
        
        bool dp[m + 1][n + 1];
        
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (i > 0) dp[i][j] = dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1]);
                if (j > 0 && !dp[i][j]) dp[i][j] = dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]);
            }
        }

        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }

        return dp[m][n];
    }
};

int 
main(int argc, char *argv[])
{
    Solution sol;
    string s1, s2, s3;

    s1 = "aa";
    s2 = "ab";
    s3 = "aaba";

    cout << sol.isInterleave(s1, s2, s3) << endl;

    return 0;
}
